#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<forward_list>
using namespace std;

class listNode{
public:
    listNode(int key,int value){
        this->node.first = key;
        this->node.second = value;
        next = nullptr;
    }
public:
    listNode* next;
    pair<int,int> node;

};

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        V = vector<listNode*>(739,nullptr);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        if(V[key%739]==nullptr){
            V[key%739] = new listNode(key,value);
        }
        else{
            auto curr = V[key%739];
            int status = 0;
            while(curr->next!=nullptr){
                if((curr->node.first)==key){
                    curr->node.second = value;
                    status =1;
                    break;
                }
                curr = curr->next;
            }
            if(status == 0){
                if(curr->node.first==key){
                    curr->node.second = value;
                }
                else{
                    curr->next = new listNode(key,value);
                }
            }

        }
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        auto curr = V[key%739];
        while(curr!=nullptr){
            if(curr->node.first==key){
                return curr->node.second;
            }
            curr = curr->next;
        }
        return -1;

    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        if(get(key)==-1){
            return;
        }
        else{
            auto curr = V[key%739];
            if(curr->node.first==key){
                V[key%739] = curr->next;
                curr = nullptr;
                return;
            }
            listNode* pre = nullptr;

            while(curr!=nullptr){
                if(curr->node.first==key){
                    pre->next = curr->next;
                    break;
                }
                pre = curr;
                curr = curr->next;
            }
        }
    }
public:
    vector<listNode*> V;
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */


int main(){
    MyHashMap M;
    M.put(1,1);
    M.put(2,2);
    cout<<M.get(1)<<endl;
    cout<<M.get(3)<<endl;
    M.put(2,1);
    cout<<M.get(2)<<endl;
    M.remove(2);
    cout<<M.get(2)<<endl;
}